//https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/submissions/575087400/


class Solution {
public:
    int findIntegers(int n) {
        int m = __lg(n); // n 的最高位，使用 __lg(n) 来找到 n 的最高有效位的索引
        vector<array<int, 2>> memo(m + 1, {-1, -1}); // 记忆化数组，大小为 m + 1，初始值为 -1，表示没有计算过

        // 使用 lambda 表达式实现递归的深度优先搜索
        auto dfs = [&](auto&& dfs, int i, bool pre1, bool is_limit) -> int {
            if (i < 0) {
                return 1; // 当所有位都处理完毕，返回 1，表示找到一个合法方案
            }
            if (!is_limit && memo[i][pre1] >= 0) { // 如果当前不受限制且之前已经计算过该状态，直接返回结果
                return memo[i][pre1];
            }
            int up = is_limit ? n >> i & 1 : 1; // 当前位的上限，如果受限则为 n 的对应位，否则为 1
            int res = dfs(dfs, i - 1, false, is_limit && up == 0); // 填 0，递归计算下一位
            if (!pre1 && up == 1) { // 如果前一位不是 1，且当前位可以填 1
                res += dfs(dfs, i - 1, true, is_limit); // 填 1，递归计算下一位
            }
            if (!is_limit) {
                memo[i][pre1] = res; // 如果当前不受限制，将结果进行记忆化保存
            }
            return res;
        };
        return dfs(dfs, m, false, true); // 从最高位开始递归，初始状态前一位不是 1，受限
    }
};